package parsetree;

import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;

import javax.swing.event.DocumentEvent.ElementChange;
import javax.swing.text.AbstractDocument.DefaultDocumentEvent;
import javax.swing.text.AbstractDocument.ElementEdit;
import javax.swing.text.AttributeSet;
import javax.swing.text.BadLocationException;
import javax.swing.text.Document;

import metagrammar.Type;
import parsetree.exceptions.DocumentContractBrokenException;

import com.google.common.collect.ImmutableList;

public abstract class AbstractBranchElement extends AbstractElement implements BranchElement {
    
    private static final Comparator<Element> childToDummyComparator = new Comparator<Element>() {
        @Override
        public int compare(Element o1, Element o2)
        {
            if(o1.getStartOffset() < o2.getStartOffset()) {
                if(o1.getEndOffset() > o2.getEndOffset()) {
                    return 0;
                }
                else {
                    return -1;
                }
            }
            else {
                return 1;
            }
        }
    };
    private static final Comparator<Element> childToDummyStartComparator = new Comparator<Element>() {
        @Override
        public int compare(Element o1, Element o2)
        {
            return o1.getStartOffset() - o2.getStartOffset();
        }
    };
    private static final Comparator<Element> childToDummyEndComparator = new Comparator<Element>() {
        @Override
        public int compare(Element o1, Element o2)
        {
            return o1.getEndOffset() - o2.getEndOffset();
        }
    };
    private ArrayList<Element> children;
    
    /**
     * @param children
     */
    protected AbstractBranchElement(BranchElement parent, Collection<Element> children)
    {
        super(parent.getParseTree(), parent);
        if(children == null) {
            throw new NullPointerException("AbstractBranchElement cannot have null children");
        }
        if(children instanceof ArrayList) {
            this.children = (ArrayList<Element>) children;
        }
        else {
            this.children = new ArrayList<Element>(children);
        }
        ensureParenthood();
    }
    
    protected AbstractBranchElement(BranchElement parent, Collection<Element> children,
            AttributeSet attributes)
    {
        super(parent.getParseTree(), parent, attributes);
        if(children == null) {
            throw new NullPointerException("AbstractBranchElement cannot have null children");
        }
        if(children instanceof ArrayList) {
            this.children = (ArrayList<Element>) children;
        }
        else {
            this.children = new ArrayList<Element>(children);
        }
        ensureParenthood();
    }
    
    protected AbstractBranchElement(ParseTree parseTree, BranchElement parent,
            Collection<Element> children)
    {
        super(parseTree, parent);
        if(children == null) {
            throw new NullPointerException("AbstractBranchElement cannot have null children");
        }
        if(children instanceof ArrayList) {
            this.children = (ArrayList<Element>) children;
        }
        else {
            this.children = new ArrayList<Element>(children);
        }
        ensureParenthood();
    }
    
    private void ensureParenthood()
    {
        int children = getElementCount();
        for(int i = 0; i < children; i++) {
            getElement(i).setParent(this);
        }
    }
    
    /**
     * Adds a element as a child of this Element. Since the child list must be kept
     * in sorted order, the index of the element will be automatically derived from the
     * child's {@link Element#getStartOffset() getStartOffset()} and
     * {@link Element#getEndOffset() getEndOffset()} methods. (If those two methods do not
     * provide a valid modelOffset the child will simply be inserted at the end of the
     * list, which could unpredictable behavior and should not be used.) In the case of
     * a successful insert, the method will then try to {@link Element#merge(Element) merge}
     * the inserted Element with the Elements before and after it in the child list.
     * @param elem the element which will be a child of the current element
     * @return true if a position could be derived, false if the element was inserted at
     *         the end of the child list.
     * @see {@link #addChildren(Element[], boolean, boolean)} which, besides allowing
     * the insertion of multiple elements also allows the user to specify finer control
     * over the merge behavior.
     */
    @Override
    public ElementEdit addChild(Element elem)
    {
        if(elem == null) {
            throw new NullPointerException("AbstractBranchElement cannot have a null child");
        }
        
        if(children.isEmpty()) {
            // if there are no children add this child
            addChildToChildren(elem);
            return new ElementEdit(this, elem.getStartOffset(), null, new Element[] { elem });
        }
        
        HashSet<Element> addedChildren = new HashSet<Element>();
        HashSet<Element> removedChildren = new HashSet<Element>();
        
        int startOffset = elem.getStartOffset();
        if(startOffset != -1) {
            //if there is a valid start position for the element
            int endOffset = elem.getEndOffset();
            int startIndex = getIndexOfChildContaining(startOffset);
            int actualStartIndex, actualEndIndex;
            if(startIndex >= 0) {
                // if (startIndex > 0) an element contains startIndex and there may need be a split
                actualStartIndex = startIndex + 1;
                Element startElement = children.get(startIndex);
                if(startElement.getStartOffset() != startOffset
                        && startElement.getEndOffset() != startOffset) {
                    // if the the modelOffset is not an edge of the Element, split 
                    children.remove(startIndex);
                    try {
                        List<Element> startSplit = Arrays.asList(startElement
                                .split(startOffset));
                        addElementsToChildren(startIndex, startSplit);
                        addedChildren.addAll(startSplit);
                    }
                    catch(BadLocationException e) {
                        throw new DocumentContractBrokenException();
                    }
                }
            }
            else {
                actualStartIndex = (-startIndex) - 1;
            }
            int endIndex = getIndexOfChildContaining(endOffset);
            if(endIndex >= 0) {
                actualEndIndex = endIndex;
                // the same applies for endIndex
                Element splitElement = children.get(endIndex);
                if(splitElement.getStartOffset() != endOffset
                        && splitElement.getEndOffset() != endOffset) {
                    children.get(endIndex);
                    try {
                        Element[] split = splitElement.split(endOffset);
                        int index = 0;
                        while(split[index].getStartOffset() < endOffset) {
                            index++;
                        }
                        Element removedElem = children.set(endIndex, split[index]);
                        removedChildren.add(removedElem);
                        addedChildren.addAll(Arrays.asList(split));
                    }
                    catch(BadLocationException e) {
                        throw new DocumentContractBrokenException();
                    }
                }
            }
            else {
                actualEndIndex = (-endIndex) - 1;
            }
            if(actualStartIndex != actualEndIndex) {
                // element(s) exist which must be removed
                for(int i = actualStartIndex; i < actualEndIndex; i++) {
                    Element removedElem = children.remove(actualStartIndex);
                    removedChildren.add(removedElem);
                }
            }
            // merge logic TODO
            Element mergedElement = elem;
            while(actualStartIndex > 0 && mergedElement != null) {
                Element priorChild = children.get(actualStartIndex - 1);
                mergedElement = priorChild.merge(elem);
                if(mergedElement != null) {
                    removedChildren.add(elem);
                    elem = mergedElement;
                    children.remove(actualStartIndex - 1);
                    actualStartIndex--;
                }
            }
            mergedElement = elem;
            while((children.size() - 1) > actualStartIndex && mergedElement != null) {
                Element nextChild = children.get(actualStartIndex);
                mergedElement = nextChild.merge(elem);
                if(mergedElement != null) {
                    elem = mergedElement;
                    Element removedElem = children.remove(actualStartIndex);
                    removedChildren.add(removedElem);
                }
            }
            addChildToChildren(elem, actualStartIndex);
            addedChildren.add(elem);
            return new ElementEdit(this, getStartOffset(), removedChildren.toArray(new Element[0]),
                    addedChildren.toArray(new Element[0]));
        }
        else {
            // if the start offset is not defined the new child is simply added to the end of
            // the child list.
            // REREAD: should this throw an exception instead?
            addChildToChildren(elem);
            return new ElementEdit(this, elem.getStartOffset(), null, new Element[] { elem });
        }
    }
    
    /**
     * @param elem
     * @param index
     */
    private void addChildToChildren(Element elem, int index)
    {
        elem.setParent(this);
        children.add(index, elem);
    }
    
    /**
     * @param elem
     */
    private boolean addChildToChildren(Element elem)
    {
        elem.setParent(this);
        return children.add(elem);
    }
    
    @Override
    public ElementEdit addChildren(Element[] elems, boolean mergeLeft, boolean mergeRight)
    {
        if(elems.length == 0) {
            return null;
        }
        
        boolean sorted = true;
        for(int i = 0; sorted && i < elems.length - 1; i++) {
            sorted &= elems[i].getEndOffset() == elems[i + 1].getStartOffset();
        }
        if(!sorted) {
            throw new IllegalArgumentException(
            "AbstractBranchElement.addChildren(Element[]) only accepts sorted, continuous arrays.");
        }
        
        if(children.isEmpty()) {
            // if there are no children add this child
            addElementsToChildren(elems);
            return new ElementEdit(this, elems[0].getStartOffset(), null, elems);
        }
        
        HashSet<Element> addedChildren = new HashSet<Element>();
        HashSet<Element> removedChildren = new HashSet<Element>();
        
        int startOffset = elems[0].getStartOffset();
        if(startOffset != -1) {
            //if there is a valid start position for the element
            int endOffset = elems[elems.length - 1].getEndOffset();
            int startIndex = getIndexOfChildContaining(startOffset);
            int actualStartIndex, actualEndIndex;
            if(startIndex >= 0) {
                // if (startIndex > 0) an element contains startIndex and there may need be a split
                actualStartIndex = startIndex + 1;
                Element startElement = children.get(startIndex);
                if(startElement.getStartOffset() != startOffset
                        && startElement.getEndOffset() != startOffset) {
                    // if the the modelOffset is not an edge of the Element, split 
                    children.remove(startIndex);
                    try {
                        List<Element> startSplit = Arrays.asList(startElement
                                .split(startOffset));
                        addElementsToChildren(startIndex, startSplit);
                        addedChildren.addAll(startSplit);
                    }
                    catch(BadLocationException e) {
                        throw new DocumentContractBrokenException();
                    }
                }
            }
            else {
                actualStartIndex = (-startIndex) - 1;
            }
            int endIndex = getIndexOfChildContaining(endOffset);
            if(endIndex >= 0) {
                actualEndIndex = endIndex;
                // the same applies for endIndex
                Element splitElement = children.get(endIndex);
                if(splitElement.getStartOffset() != endOffset
                        && splitElement.getEndOffset() != endOffset) {
                    children.get(endIndex);
                    try {
                        Element[] split = splitElement.split(endOffset);
                        int index = 0;
                        while(split[index].getStartOffset() < endOffset) {
                            index++;
                        }
                        Element removedElem = children.set(endIndex, split[index]);
                        removedChildren.add(removedElem);
                        addedChildren.addAll(Arrays.asList(split));
                    }
                    catch(BadLocationException e) {
                        throw new DocumentContractBrokenException();
                    }
                }
            }
            else {
                actualEndIndex = (-endIndex) - 1;
            }
            if(actualStartIndex != actualEndIndex) {
                // element(s) exist which must be removed
                for(int i = actualStartIndex; i < actualEndIndex; i++) {
                    Element removedElem = children.remove(actualStartIndex);
                    removedChildren.add(removedElem);
                }
            }
            for(int i = 0; i < elems.length; i++) {
                elems[i].setParent(this);
            }
            addElementsToChildren(elems, actualStartIndex);
            addedChildren.addAll(Arrays.asList(elems));
            return new ElementEdit(this, getStartOffset(), removedChildren.toArray(new Element[0]),
                    addedChildren.toArray(new Element[0]));
        }
        else {
            // if the start offset is not defined the new child is simply added to the end of
            // the child list.
            // REREAD: should this throw an exception?
            addElementsToChildren(elems);
            return new ElementEdit(this, elems[0].getStartOffset(), null, elems);
        }
    }
    
    /**
     * @param startIndex
     * @param startSplit
     */
    private void addElementsToChildren(int startIndex, Collection<Element> elements)
    {
        for(Element element : elements) {
            element.setParent(this);
        }
        children.addAll(startIndex, elements);
    }
    
    /**
     * @param elems
     * @param actualStartIndex
     */
    private void addElementsToChildren(Element[] elems, int actualStartIndex)
    {
        for(int i = 0; i < elems.length; i++) {
            elems[i].setParent(this);
        }
        children.addAll(actualStartIndex, Arrays.asList(elems));
    }
    
    /**
     * @param elems
     * @return
     */
    private boolean addElementsToChildren(Element[] elems)
    {
        for(int i = 0; i < elems.length; i++) {
            elems[i].setParent(this);
        }
        return children.addAll(Arrays.asList(elems));
    }
    
    /**
     * @param elem
     * @param childToReplace
     * @return
     */
    protected boolean validateReplacement(int index, Element elem)
    {
        return true;
    }
    
    /* (non-Javadoc)
     * @see gui.text.BranchElement#getChildContaining(int)
     */
    @Override
    public Element getChildContaining(int documentOffset)
    {
        int index = getIndexOfChildContaining(documentOffset);
        if(index >= 0 && index < children.size()) {
            return children.get(index);
        }
        return null;
    }
    
    /* (non-Javadoc)
     * @see gui.text.BranchElement#getChildStartsWith(int)
     */
    @Override
    public Element getChildStartsWith(int documentOffset)
    {
        int index = getIndexOfChildStartsWith(documentOffset);
        if(index >= 0 && index < children.size()) {
            return children.get(index);
        }
        return null;
    }
    
    /* (non-Javadoc)
     * @see gui.text.BranchElement#getChildEndsWith(int)
     */
    @Override
    public Element getChildEndsWith(int documentOffset)
    {
        int index = getIndexOfChildEndsWith(documentOffset);
        if(index >= 0 && index < children.size()) {
            return children.get(index);
        }
        return null;
    }
    
    /* (non-Javadoc)
     * @see gui.text.BranchElement#getChildCount()
     */
    @Override
    public int getChildCount()
    {
        return children.size();
    }
    
    @Override
    public ImmutableList<Element> getChildren()
    {
        return ImmutableList.copyOf(children);
    }
    
    /* (non-Javadoc)
     * @see gui.text.BranchElement#getElement(int)
     */
    @Override
    public Element getElement(int index)
    {
        if(index >= 0) {
            if(index < children.size()) {
                return children.get(index);
            }
            return children.get(children.size() - 1);
        }
        return children.isEmpty() ? null : children.get(0);
    }
    
    @Override
    public int getElementCount()
    {
        return getChildCount();
    }
    
    
    @Override
    public int getElementIndex(int offset)
    {
        int index = getIndexOfChildContaining(offset);
        if(index < 0) {
            index = -(index + 1);
        }
        if(index >= children.size()) {
            index = children.size() - 1;
        }
        return index;
    }
    
    
    @Override
    public int getEndOffset()
    {
        return children.isEmpty() ? -1 : children.get(children.size() - 1).getEndOffset();
    }
    
    @Override
    public int getStartOffset()
    {
        return children.isEmpty() ? -1 : children.get(0).getStartOffset();
    }
    
    /* (non-Javadoc)
     * @see gui.text.BranchElement#hasChildren()
     */
    @Override
    public boolean hasChildren()
    {
        return children.size() != 0;
    }
    
    @Override
    public int getIndexOfChildContaining(int documentOffset)
    {
        List<Element> childList = children;
        return Collections.binarySearch(childList, new DummySearchElement(documentOffset),
                childToDummyComparator);
    }
    
    /**
     * Passes along the {@linkplain DefaultDocumentEvent} caused by an insert update
     * to the children of this, if relevant. The method first checks if there is a
     * child that completely contains the {@linkplain DefaultDocumentEvent#getOffset() offset}
     * and, if so, passes it to that child. Otherwise it passes the change to both the child
     * that starts with the {@linkplain DefaultDocumentEvent#getOffset() offset} and the one
     * that ends with it, if they exist.
     * @param change a {@linkplain DefaultDocumentEvent} from an
     * {@linkplain #insertUpdate(DefaultDocumentEvent, AttributeSet) insertUpdate} which
     * prompted the need to update
     * @param attributes the {@linkplain AttributeSet} for this change
     * @return true iff one or more of the children of this were change as a result of
     * the insertUpdate.
     */
    public List<ElementChange> insertUpdateChildren(Insert change,
            AttributeSet attributes)
            {
        int offset = change.getOffset();
        Element toChange = getChildContaining(offset);
        List<ElementChange> changes = null;
        if(toChange != null) {
            changes = toChange.insertUpdate(change, attributes);
        }
        else {
            toChange = getChildStartsWith(offset);
            if(toChange != null) {
                changes = toChange.insertUpdate(change, attributes);
            }
            else {
                toChange = getChildStartsWith(offset + change.getLength());
                if(toChange != null) {
                    changes = toChange.insertUpdate(change, attributes);
                }
            }
            if(changes == null || changes.isEmpty()) {
                toChange = getChildEndsWith(offset);
                if(toChange != null) {
                    changes = toChange.insertUpdate(change, attributes);
                }
            }
        }
        return changes;
            }
    
    @Override
    public boolean isLeaf()
    {
        return children.isEmpty();
    }
    
    public List<ElementChange> postRemoveUpdateChildren(Removal change)
    {
        int offset = change.getOffset();
        List<ElementChange> changes = null;
        Element toChange = getChildContaining(offset);
        if(toChange != null) {
            changes = toChange.postRemoveUpdate(change);
        }
        else {
            toChange = getChildStartsWith(offset);
            if(toChange != null) {
                changes = toChange.postRemoveUpdate(change);
            }
            toChange = getChildEndsWith(offset);
            if(toChange != null) {
                if(changes == null) {
                    changes = toChange.postRemoveUpdate(change);
                }
                else {
                    changes.addAll(toChange.postRemoveUpdate(change));
                }
            }
        }
        return changes;
    }
    
    @Override
    public int getIndexOfChildStartsWith(int documentOffset)
    {
        List<Element> childList = children;
        int index = Collections.binarySearch(childList, new DummySearchElement(documentOffset),
                childToDummyStartComparator);
        while(index > 0 && getElement(index - 1).getStartOffset() == documentOffset) {
            index--;
        }
        return index;
    }
    
    @Override
    public int getIndexOfChildEndsWith(int documentOffset)
    {
        List<Element> childList = children;
        return Collections.binarySearch(childList, new DummySearchElement(documentOffset),
                childToDummyEndComparator);
    }
    
    @Override
    public ElementEdit removeEmptyChild(Element elem)
    {
        int startOffset = elem.getStartOffset();
        if(startOffset == elem.getEndOffset()) {
            int index = getIndexOfChildStartsWith(startOffset);
            if(getElement(index) == elem) {
                children.remove(index);
                return new ElementEdit(this, elem.getStartOffset(), new Element[] { elem }, null);
            }
        }
        return null;
    }
    
    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString()
    {
        return getName() + "(" + getStartOffset() + ", " + getEndOffset() + ", "
        + (children != null ? "children=" + children : "") + ")";
    }
    
    @Override
    public void writeExternal(ObjectOutput out) throws IOException
    {
        super.writeExternal(out);
        out.writeObject(children);
    }
    
    @Override
    public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException
    {
        super.readExternal(in);
        children = (ArrayList<Element>) in.readObject();
    }
    
    
    
    /**
     * Dummy element used in binary searches.
     */
    private class DummySearchElement implements Element {
        
        private final int index;
        
        /**
         * @param modelOffset the modelOffset within the document to be searched for.
         */
        public DummySearchElement(int modelOffset)
        {
            this.index = modelOffset;
        }
        
        @Deprecated
        @Override
        public AttributeSet getAttributes()
        {
            return null;
        }
        
        @Deprecated
        @Override
        public int getChildCount()
        {
            return 0;
        }
        
        @Deprecated
        @Override
        public Document getDocument()
        {
            return null;
        }
        
        @Deprecated
        @Override
        public Element getElement(int index)
        {
            return null;
        }
        
        @Deprecated
        @Override
        public int getElementCount()
        {
            return 0;
        }
        
        @Deprecated
        @Override
        public int getElementIndex(int offset)
        {
            return 0;
        }
        
        @Override
        public int getEndOffset()
        {
            return index;
        }
        
        @Deprecated
        @Override
        public Type getType()
        {
            return null;
        }
        
        @Deprecated
        @Override
        public String getName()
        {
            return null;
        }
        
        @Deprecated
        @Override
        public AbstractBranchElement getParent()
        {
            return null;
        }
        
        @Deprecated
        @Override
        public javax.swing.text.Element getParentElement()
        {
            return null;
        }
        
        @Override
        public int getStartOffset()
        {
            return index;
        }
        
        @Deprecated
        @Override
        public boolean hasChildren()
        {
            return false;
        }
        
        @Deprecated
        @Override
        public boolean isLeaf()
        {
            return true;
        }
        
        @Deprecated
        @Override
        public Element[] split(int modelOffet)
        {
            return null;
        }
        
        @Deprecated
        @Override
        public void setAttributes(AttributeSet attributes)
        {
            //does nothing
        }
        
        @Deprecated
        @Override
        public Element merge(Element element)
        {
            return null;
        }
        
        @Deprecated
        @Override
        public BranchElement setParent(AbstractBranchElement newParent)
        {
            return null;
        }
        
        @Deprecated
        @Override
        public List<ElementChange> insertUpdate(Insert change, AttributeSet attributes)
        {
            return null;
        }
        
        @Deprecated
        @Override
        public List<ElementChange> postRemoveUpdate(Removal change)
        {
            return null;
        }
        
        @Deprecated
        @Override
        public ParseTree getParseTree()
        {
            // TODO Auto-generated method stub
            return null;
        }
        
        @Deprecated
        @Override
        public void writeExternal(ObjectOutput out) throws IOException
        {
        }
        
        @Deprecated
        @Override
        public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException
        {
        }
        
        @Override
        public void addAttributes(AttributeSet newAttributes)
        {
        }
        
    }
    
    
}